Algorithms developed to tackle tenuous group query

Finding tenuous groups, those with few social interactions and weak relationships among members, has been a hot topic in community search for reviewer selection and psycho-educational group formation. The existing metrics (e.g., k-triangle, k-line, and k-tenuity) used to measure the tenuity require a suitable k value to be specified, which is difficult for users without background knowledge.

A research team led by Huaijie Zhu has proposed several approaches to tackle this problem. The first is an exact algorithm, named MTG-VDIS, which selects those vertices whose vertex distance is large to generate the result group. It also utilizes effective filtering and pruning strategies.

Since MTG-VDIS is not fast enough, the team designed an efficient exact algorithm, called MTG-VDGE, which exploits the degree metric to sort the vertexes and proposes a new combination order, namely degree and reverse based branch and bound (DRBB). MTG-VDGE gives priority to those vertices with a small degree. For a large p, the team developed an approximation algorithm, named MTG-VDLT, that discards candidate attendees with high degree to reduce the number of vertices to be considered.

The algorithms are published in Frontiers of Computer Science.

In the experiments, the researchers compared the proposed algorithms with the following performance metrics: (1) query time, (2) distance of the result, (3) average group distance of the result, (4) the accuracy score S of the result of the approximation algorithm.

They also conducted a case study to show the usefulness of MTG-VDLT and MTG-VDGE on LA dataset. Experimental results on real datasets manifest that MTG-VDGE outperforms MTG-VDIS in efficiency. For MTG-VDLT, compared with KLMA, the result obtained by MTG-VDLT has a higher accuracy score.

Future work may focus on finding more suitable and flexible metrics to obtain a tenuous group, such as using a machine-learning based method to learn the k value from users' history data.